package LeetCode;

public class LC_153_FindMinimuminRotatedSortedArray {

    public static void main(String[] args) {

    }

    static class Solution {
        public int findMin(int[] num) {
            return findMin(num, 0, num.length - 1);
        }

        public int findMin(int[] num, int left, int right) {
            if (left == right)
                return num[left];
            if ((right - left) == 1)
                return Math.min(num[left], num[right]);
            int middle = left + (right - left) / 2;
            if (num[left] < num[right]) {
                return num[left];
            } else if (num[middle] > num[left]) {
                return findMin(num, middle, right);
            } else {
                return findMin(num, left, middle);
            }
        }
    }

    static class Solution_2 {
        public int findMin(int[] nums) {
            if (nums == null || nums.length == 0)
                return -1;
            if (nums.length == 1)
                return nums[0];
            int left = 0;
            int right = nums.length - 1;
            if (nums[left] < nums[right])
                return nums[left];
            while (left <= right) {
                if (right - left == 1)
                    return nums[right];
                int m = left + (right - left) / 2;
                if (nums[m] > nums[right])
                    left = m;
                else
                    right = m;
            }
            return nums[left];
        }
    }

    static class Solution_3 {
        public int findMin(int[] nums) {
            if (nums == null || nums.length == 0)
                return -1;
            int i = 0;
            int j = nums.length - 1;
            while (i <= j) {
                if (nums[i] <= nums[j])
                    return nums[i];
                int m = (i + j) / 2;
                if (nums[m] >= nums[i]) {
                    i = m + 1;
                } else {
                    j = m;
                }
            }
            return -1;
        }
    }

}